from tools_algorithm import *


class Solution:
    def minimumWeight(
        self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int
    ) -> int:
        s = [src1, src2]
        f = [[] for _ in range(3)]

        nexts = [[] for _ in range(n)]
        stxen = [[] for _ in range(n)]

        for a, b, w in edges:
            nexts[a].append((b, w))
            stxen[b].append((a, w))

        def run(src, nexts):
            ans = [inf] * n
            ans[src] = 0
            q = [(0, src)]
            while q:
                aw, a = heappop(q)
                if aw == ans[a]:
                    for b, w in nexts[a]:
                        if aw + w < ans[b]:
                            ans[b] = aw + w
                            heappush(q, (aw + w, b))
            return ans

        for i, v in enumerate(s):
            f[i] = run(v, nexts)
        f[2] = run(dest, stxen)
        ans = inf
        for i in range(n):
            t = 0
            for j in range(3):
                t += f[j][i]
            ans = min(ans, t)
        return -1 if ans == inf else ans


s = Solution()
print(
    s.minimumWeight(
        n=6,
        edges=[
            [0, 2, 2],
            [0, 5, 6],
            [1, 0, 3],
            [1, 4, 5],
            [2, 1, 1],
            [2, 3, 3],
            [2, 3, 4],
            [3, 4, 2],
            [4, 5, 1],
        ],
        src1=0,
        src2=1,
        dest=5,
    )
)
